/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-05-13 11:05:03
 * @LastEditors: lily
 * @LastEditTime: 2021-05-13 15:54:38
 */
/*
 * @lc app=leetcode.cn id=78 lang=javascript
 *
 * [78] 子集
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */

//  思想：回溯法
//  https://leetcode-cn.com/problems/subsets/solution/shou-hua-tu-jie-zi-ji-hui-su-fa-xiang-jie-wei-yun-/
//  用 for 枚举出当前可选的数,通过控制循环的起点，使得最后递归自然结束

//  复杂度： O(n2^n) O(n)

var subsets = function (nums) {
    let res = []
    var dfs = (index, currArr) => {
        // 深拷贝
        res.push(currArr.slice())
        // 枚举可选的数
        for (let i = index; i < nums.length; i++) {
            // 加入当前数
            currArr.push(nums[i])
            // 基于当前数继续选取
            dfs(i + 1, currArr)
            // 回溯
            currArr.pop()
        }
    }
    dfs(0, [])
    return res
};
// @lc code=end

console.log(subsets([1, 2, 3]));